package io.github.hadyang.leetcode.offer;

import org.junit.Test;

/**
 * https://leetcode-cn.com/problems/search-a-2d-matrix-ii/
 *
 * @author haoyang.shi
 */
public class Array240 {

  @Test
  public void test() {
    int[][] nums = {
      {1, 4, 7, 11, 15},
      {2, 5, 8, 12, 19},
      {3, 6, 9, 16, 22},
      {10, 13, 14, 17, 24},
      {18, 21, 23, 26, 30}
    };

    System.out.println(searchMatrix(nums, 3));
    System.out.println(searchMatrix(nums, 0));
    System.out.println(searchMatrix(nums, 31));
    System.out.println(searchMatrix(nums, 5));
    System.out.println(searchMatrix(nums, 11));
    System.out.println(searchMatrix(nums, 12));

    System.out.println(searchMatrix(new int[][] {{-1, 3}}, 3));
    System.out.println(searchMatrix(new int[][] {{-1}}, -1));
    System.out.println(searchMatrix(new int[][] {{1}, {2}}, 2));
  }

  public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix.length == 0) {
      return false;
    }

    for (int i = 0, j = matrix[0].length - 1; i < matrix.length && j >= 0; ) {
      if (matrix[i][j] > target) {
        j--;
      } else if (matrix[i][j] < target) {
        i++;
      } else {
        return true;
      }
    }

    return false;
  }
}
